/*-
 * Copyright 2012 Guram Dukashvili
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */
//---------------------------------------------------------------------------
#include "sys.h"
#include "str.h"
#include "idx.h"
//---------------------------------------------------------------------------
static void index_insert_key(
  struct index_link * link,
  uint32_t position,
  const void * key,
  const void * data,
  const byte_size_int * next_level_block_index)
{
  uintptr_t entry_size = link->idx->entries_sizes[link->blk.type];
  uint8_t * p = link->blk.keys + position * entry_size;

#if COMPILE_RUNTIME_CHECKS
  if( key == NULL ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( position > link->blk.count ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
  if( link->blk.count > link->idx->blk_max_keys[link->blk.type] ){
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  memmove(p + entry_size,p,(link->blk.count - position) * entry_size);
  memcpy(p,key,link->idx->key_size);
  p += link->idx->key_size;

  if( link->blk.type == INDEX_LEAF ){
#if COMPILE_RUNTIME_CHECKS
    if( data == NULL ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
    memcpy(p,data,link->idx->data_size);
  }
  else if( link->blk.type == INDEX_NODE ){
#if COMPILE_RUNTIME_CHECKS
    if( next_level_block_index == NULL ){
      fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
      abort();
    }
#endif
    memcpy(p,next_level_block_index,link->idx->block_index_size);
    p += link->idx->block_index_size;
  }
#if COMPILE_RUNTIME_CHECKS
  else {
    fprintf(stderr,"undefined behavior in %s, line %d\n",__FILE__,__LINE__);
    abort();
  }
#endif

  link->blk.count++;
  link->serno++;
}
//---------------------------------------------------------------------------
static void scatter_block(
  struct index * idx,
  struct index_btree_stack_entry * e)
{
  uintptr_t half = e->link->blk.count / 2;
  byte_size_int * new_block_index = alloca(idx->block_index_size);

  bool root = bsint_is_zero(&e->link->block_index,idx->block_index_size);

  if( root ){
    index_block_allocate(idx,new_block_index);
    e->left = index_link_block_noread(idx,new_block_index);
    e->left->blk.type = e->link->blk.type;
    e->left->blk.count = 0;
#if COMPILE_RUNTIME_CHECKS
    memset(e->left->blk.keys,0,
      e->left->idx->blk_max_keys[e->left->blk.type]
        * e->left->idx->entries_sizes[e->left->blk.type]);
#endif
    //rwlock_acquire_write_lock(&e->left->lock);
    //e->left_lock = RWL_WRITE;
  }

  index_block_allocate(idx,new_block_index);
  e->right = index_link_block_noread(idx,new_block_index);
  e->right->blk.type = e->link->blk.type;
  e->right->blk.count = 0;
#if COMPILE_RUNTIME_CHECKS
  memset(e->right->blk.keys,0,
    e->right->idx->blk_max_keys[e->right->blk.type]
      * e->right->idx->entries_sizes[e->right->blk.type]);
#endif
  //rwlock_acquire_write_lock(&e->right->lock);
  //e->right_lock = RWL_WRITE;

  if( root ){

    index_cut_paste_keys(e->right,0,e->link,half,e->link->blk.count - half);
    index_cut_paste_keys(e->left,0,e->link,0,e->link->blk.count);

    if( e->link->blk.type == INDEX_LEAF ) e->link->blk.type = INDEX_NODE;

    index_insert_key(e->link,0,index_block_entry(e->left,0),NULL,&e->left->block_index);
    index_insert_key(e->link,1,index_block_entry(e->right,0),NULL,&e->right->block_index);

    e->left_change = ILC_NEW;
  }
  else {
    index_cut_paste_keys(e->right,0,e->link,half,e->link->blk.count - half);
  }

  e->link_change = ILC_UPD;
  e->right_change = ILC_NEW;
}
//---------------------------------------------------------------------------
void index_scatter(
  struct index * idx,
  struct index_btree_stack * stack,
  const void * key,
  const void * data)
{
  int err = EEXIST;
  intptr_t sp;
  uintptr_t insert_position = 0;
  enum RWLOCK_TYPE lock_type = RWL_WRITE;
  struct index_btree_stack_entry * e, * t;
  struct index * mvcc_idx;
  
  index_lookup(idx,stack,key,0,NULL);
  if( errno == ENOENT ){
    mvcc_idx = index_get_mvcc(idx);

    index_get_key_path(mvcc_idx,stack,key,0);

    sp = stack->sp;
    e = array_get(&stack->entries,stack->sp);

    if( errno != 0 ){
      err = errno;
    }
    else if( e->c != 0 ){
      const byte_size_int * next_level = NULL;
      const void * tkey = key, * tdata = data;

      rwlock_acquire_write_lock(&mvcc_idx->readers_lock);

      rwlock_acquire_read_lock(&mvcc_idx->changed_links_lock);
      lock_type = RWL_UPGRADE;
      
      t = NULL;

      for(;;){
        struct index_link * lnk, * link = e->link;
        
        insert_position = e->position + (e->c > 0);

        if( t == NULL /*sp == stack->sp*/ || t->right != NULL ){
          if( link->blk.count == mvcc_idx->blk_max_keys[link->blk.type] ){
            scatter_block(mvcc_idx,e);

            lnk = sp == 0 ? e->left : link;

            if( insert_position >= lnk->blk.count ){
              link = e->right;
              insert_position -= lnk->blk.count;
            }
            else {
              link = lnk;
            }
          }

          index_insert_key(link,insert_position,tkey,tdata,next_level);

          e->link_change = ILC_UPD;
          if( e->left != NULL && e->right != NULL
              && e->position + (e->c > 0) == 0 ) // update up level key if root split
            memcpy(e->link->blk.keys,link->blk.keys,mvcc_idx->key_size);

  //        if( e->right != NULL ){
  //          DEBUG_index_dump_block_keys(stderr,e->link);
  //          DEBUG_index_dump_block_keys(stderr,e->left);
  //          DEBUG_index_dump_block_keys(stderr,e->right);
  //
  //          fprintf(stderr,"c = %" PRIiPTR ", p = %" PRIuPTR "\n",e->c,e->position);
  //
  //          index_write_block(mvcc_idx,e->link);
  //          index_write_block(mvcc_idx,e->left);
  //          index_write_block(mvcc_idx,e->right);
  //        }
        }

        if( sp == 0 ) break;

        t = e;
        next_level = &t->right->block_index;
        tkey = t->right->blk.keys;
        tdata = NULL;

        sp--;
        e = array_get(&stack->entries,sp);

        if( t->link_change != ILC_NONE && t->next_level_position == 0 ){ // update up level key
          memcpy(index_block_entry(e->link,e->next_level_position),t->link->blk.keys,mvcc_idx->key_size);
          e->link_change = ILC_UPD;
        }
      }

      err = 0;

      rwlock_acquire(&mvcc_idx->changed_links_lock,lock_type);
      index_unwind_stack(mvcc_idx,stack,RWL_NONE);
      rwlock_release_write_lock(&mvcc_idx->changed_links_lock);

      rwlock_release_write_lock(&mvcc_idx->readers_lock);
    }
    index_put_mvcc(idx,mvcc_idx);
  }
  errno = err;
}
//---------------------------------------------------------------------------
